java -Xss1g -Xmx8000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp18-benchmarks/lia/chc-lia-0124.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-4413abc-m [2018-06-20 14:02:01,144 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-20 14:02:01,146 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-20 14:02:01,160 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-20 14:02:01,160 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-20 14:02:01,161 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-20 14:02:01,165 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-20 14:02:01,167 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-20 14:02:01,169 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-20 14:02:01,170 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-20 14:02:01,171 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-20 14:02:01,171 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-20 14:02:01,174 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-20 14:02:01,175 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-20 14:02:01,176 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-20 14:02:01,176 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-20 14:02:01,181 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-20 14:02:01,182 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-20 14:02:01,195 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-20 14:02:01,196 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-20 14:02:01,197 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-20 14:02:01,199 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-20 14:02:01,199 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-20 14:02:01,200 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-20 14:02:01,200 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-20 14:02:01,201 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-20 14:02:01,207 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-20 14:02:01,208 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-20 14:02:01,209 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-20 14:02:01,209 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-20 14:02:01,210 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-20 14:02:01,211 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-20 14:02:01,211 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-20 14:02:01,211 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-20 14:02:01,212 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-20 14:02:01,212 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-20 14:02:01,234 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-20 14:02:01,234 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-20 14:02:01,235 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-20 14:02:01,235 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-20 14:02:01,236 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-20 14:02:01,236 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-20 14:02:01,236 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-20 14:02:01,236 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-20 14:02:01,236 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-20 14:02:01,237 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-20 14:02:01,237 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-20 14:02:01,237 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-20 14:02:01,237 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-20 14:02:01,237 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-20 14:02:01,238 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-20 14:02:01,238 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-20 14:02:01,238 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-20 14:02:01,240 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-20 14:02:01,241 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-20 14:02:01,285 INFO ]: Repository-Root is: /tmp [2018-06-20 14:02:01,302 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-20 14:02:01,309 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-20 14:02:01,311 INFO ]: Initializing SmtParser... [2018-06-20 14:02:01,311 INFO ]: SmtParser initialized [2018-06-20 14:02:01,312 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp18-benchmarks/lia/chc-lia-0124.smt2 [2018-06-20 14:02:01,313 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-20 14:02:01,408 INFO ]: Executing SMT file /storage/chc-comp18-benchmarks/lia/chc-lia-0124.smt2 unknown [2018-06-20 14:02:01,630 INFO ]: Succesfully executed SMT file /storage/chc-comp18-benchmarks/lia/chc-lia-0124.smt2 [2018-06-20 14:02:01,634 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-20 14:02:01,640 INFO ]: Walking toolchain with 4 elements. [2018-06-20 14:02:01,641 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-20 14:02:01,641 INFO ]: Initializing ChcToBoogie... [2018-06-20 14:02:01,641 INFO ]: ChcToBoogie initialized [2018-06-20 14:02:01,644 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 20.06 02:02:01" (1/1) ... [2018-06-20 14:02:01,731 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 02:02:01 Unit [2018-06-20 14:02:01,731 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-20 14:02:01,732 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-20 14:02:01,732 INFO ]: Initializing Boogie Preprocessor... [2018-06-20 14:02:01,732 INFO ]: Boogie Preprocessor initialized [2018-06-20 14:02:01,754 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 02:02:01" (1/1) ... [2018-06-20 14:02:01,754 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 02:02:01" (1/1) ... [2018-06-20 14:02:01,761 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 02:02:01" (1/1) ... [2018-06-20 14:02:01,761 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 02:02:01" (1/1) ... [2018-06-20 14:02:01,766 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 02:02:01" (1/1) ... [2018-06-20 14:02:01,769 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 02:02:01" (1/1) ... [2018-06-20 14:02:01,771 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 02:02:01" (1/1) ... [2018-06-20 14:02:01,773 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-20 14:02:01,773 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-20 14:02:01,773 INFO ]: Initializing RCFGBuilder... [2018-06-20 14:02:01,773 INFO ]: RCFGBuilder initialized [2018-06-20 14:02:01,774 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 02:02:01" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-20 14:02:01,804 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-20 14:02:01,804 INFO ]: Found specification of procedure gotoProc [2018-06-20 14:02:01,804 INFO ]: Found implementation of procedure gotoProc [2018-06-20 14:02:01,804 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-20 14:02:01,804 INFO ]: Found specification of procedure Ultimate.START [2018-06-20 14:02:01,804 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-20 14:02:02,064 INFO ]: Using library mode [2018-06-20 14:02:02,065 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.06 02:02:02 BoogieIcfgContainer [2018-06-20 14:02:02,065 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-20 14:02:02,066 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-20 14:02:02,066 INFO ]: Initializing TraceAbstraction... [2018-06-20 14:02:02,068 INFO ]: TraceAbstraction initialized [2018-06-20 14:02:02,069 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 20.06 02:02:01" (1/3) ... [2018-06-20 14:02:02,070 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5247484f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 20.06 02:02:02, skipping insertion in model container [2018-06-20 14:02:02,070 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 02:02:01" (2/3) ... [2018-06-20 14:02:02,070 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5247484f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.06 02:02:02, skipping insertion in model container [2018-06-20 14:02:02,070 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.06 02:02:02" (3/3) ... [2018-06-20 14:02:02,072 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-20 14:02:02,080 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-20 14:02:02,089 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-20 14:02:02,128 INFO ]: Using default assertion order modulation [2018-06-20 14:02:02,128 INFO ]: Interprodecural is true [2018-06-20 14:02:02,128 INFO ]: Hoare is false [2018-06-20 14:02:02,128 INFO ]: Compute interpolants for FPandBP [2018-06-20 14:02:02,128 INFO ]: Backedges is TWOTRACK [2018-06-20 14:02:02,128 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-20 14:02:02,128 INFO ]: Difference is false [2018-06-20 14:02:02,129 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-20 14:02:02,129 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-20 14:02:02,142 INFO ]: Start isEmpty. Operand 10 states. [2018-06-20 14:02:02,152 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-20 14:02:02,152 INFO ]: Found error trace [2018-06-20 14:02:02,153 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-20 14:02:02,153 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 14:02:02,160 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-20 14:02:02,162 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 14:02:02,163 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 14:02:02,196 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 14:02:02,196 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 14:02:02,196 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 14:02:02,243 INFO ]: Conjunction of SSA is unsat [2018-06-20 14:02:02,314 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 14:02:02,323 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-20 14:02:02,323 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-20 14:02:02,325 INFO ]: Interpolant automaton has 3 states [2018-06-20 14:02:02,340 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-20 14:02:02,341 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-20 14:02:02,344 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-20 14:02:02,429 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 14:02:02,430 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-20 14:02:02,430 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-20 14:02:02,431 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-20 14:02:02,432 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 14:02:02,440 INFO ]: With dead ends: 9 [2018-06-20 14:02:02,440 INFO ]: Without dead ends: 9 [2018-06-20 14:02:02,441 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-20 14:02:02,455 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-20 14:02:02,468 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-20 14:02:02,469 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-20 14:02:02,470 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-20 14:02:02,471 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-20 14:02:02,471 INFO ]: Finished accepts. word is rejected. [2018-06-20 14:02:02,471 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-20 14:02:02,471 INFO ]: Interpolant automaton has 3 states. [2018-06-20 14:02:02,471 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-20 14:02:02,471 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-20 14:02:02,471 INFO ]: Found error trace [2018-06-20 14:02:02,471 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 14:02:02,471 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 14:02:02,473 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-20 14:02:02,473 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 14:02:02,473 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 14:02:02,474 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 14:02:02,474 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 14:02:02,474 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 14:02:02,506 INFO ]: Conjunction of SSA is unsat [2018-06-20 14:02:02,639 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 14:02:02,639 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 14:02:02,639 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 14:02:02,646 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 14:02:02,710 INFO ]: Conjunction of SSA is unsat [2018-06-20 14:02:02,721 INFO ]: Computing forward predicates... [2018-06-20 14:02:03,051 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 14:02:03,083 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 14:02:03,084 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-20 14:02:03,084 INFO ]: Interpolant automaton has 5 states [2018-06-20 14:02:03,084 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-20 14:02:03,084 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-20 14:02:03,084 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-20 14:02:03,174 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 14:02:03,174 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-20 14:02:03,174 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-20 14:02:03,174 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-20 14:02:03,174 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 14:02:03,175 INFO ]: With dead ends: 10 [2018-06-20 14:02:03,175 INFO ]: Without dead ends: 10 [2018-06-20 14:02:03,175 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-20 14:02:03,175 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-20 14:02:03,176 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-20 14:02:03,176 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-20 14:02:03,176 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-20 14:02:03,176 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-20 14:02:03,177 INFO ]: Finished accepts. word is rejected. [2018-06-20 14:02:03,177 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-20 14:02:03,177 INFO ]: Interpolant automaton has 5 states. [2018-06-20 14:02:03,177 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-20 14:02:03,177 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-20 14:02:03,177 INFO ]: Found error trace [2018-06-20 14:02:03,177 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 14:02:03,177 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 14:02:03,177 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-20 14:02:03,177 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 14:02:03,177 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 14:02:03,178 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 14:02:03,178 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 14:02:03,178 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 14:02:03,248 INFO ]: Conjunction of SSA is unsat [2018-06-20 14:02:03,545 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 14:02:03,545 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 14:02:03,545 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 14:02:03,551 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-20 14:02:03,622 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-20 14:02:03,622 INFO ]: Conjunction of SSA is unsat [2018-06-20 14:02:03,625 INFO ]: Computing forward predicates... [2018-06-20 14:02:06,532 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 14:02:06,553 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 14:02:06,553 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-20 14:02:06,553 INFO ]: Interpolant automaton has 6 states [2018-06-20 14:02:06,553 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-20 14:02:06,553 INFO ]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-20 14:02:06,553 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-20 14:02:06,587 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 14:02:06,587 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-20 14:02:06,588 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-20 14:02:06,588 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-20 14:02:06,588 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 14:02:06,588 INFO ]: With dead ends: 11 [2018-06-20 14:02:06,588 INFO ]: Without dead ends: 11 [2018-06-20 14:02:06,588 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=26, Invalid=30, Unknown=0, NotChecked=0, Total=56 [2018-06-20 14:02:06,589 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-20 14:02:06,589 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-20 14:02:06,590 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-20 14:02:06,590 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-20 14:02:06,593 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-20 14:02:06,593 INFO ]: Finished accepts. word is rejected. [2018-06-20 14:02:06,593 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-20 14:02:06,593 INFO ]: Interpolant automaton has 6 states. [2018-06-20 14:02:06,593 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-20 14:02:06,593 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-20 14:02:06,593 INFO ]: Found error trace [2018-06-20 14:02:06,593 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 14:02:06,593 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 14:02:06,593 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-20 14:02:06,593 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 14:02:06,593 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 14:02:06,594 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 14:02:06,594 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 14:02:06,594 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 14:02:06,654 INFO ]: Conjunction of SSA is unsat [2018-06-20 14:02:06,857 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 14:02:06,858 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 14:02:06,870 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 14:02:06,877 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-20 14:02:06,913 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-20 14:02:06,913 INFO ]: Conjunction of SSA is unsat [2018-06-20 14:02:06,915 INFO ]: Computing forward predicates... [2018-06-20 14:02:08,431 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 14:02:08,457 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 14:02:08,457 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-20 14:02:08,457 INFO ]: Interpolant automaton has 7 states [2018-06-20 14:02:08,458 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-20 14:02:08,458 INFO ]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-06-20 14:02:08,458 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-20 14:02:08,574 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 14:02:08,574 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-20 14:02:08,574 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-20 14:02:08,574 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-20 14:02:08,574 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 14:02:08,575 INFO ]: With dead ends: 13 [2018-06-20 14:02:08,575 INFO ]: Without dead ends: 13 [2018-06-20 14:02:08,575 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=39, Invalid=51, Unknown=0, NotChecked=0, Total=90 [2018-06-20 14:02:08,575 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-20 14:02:08,577 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-20 14:02:08,577 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-20 14:02:08,578 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-20 14:02:08,578 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 10 [2018-06-20 14:02:08,578 INFO ]: Finished accepts. word is rejected. [2018-06-20 14:02:08,578 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-20 14:02:08,578 INFO ]: Interpolant automaton has 7 states. [2018-06-20 14:02:08,578 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-20 14:02:08,578 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-20 14:02:08,578 INFO ]: Found error trace [2018-06-20 14:02:08,578 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 14:02:08,578 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 14:02:08,578 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 4 times [2018-06-20 14:02:08,578 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 14:02:08,579 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 14:02:08,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 14:02:08,579 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 14:02:08,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 14:02:08,636 INFO ]: Conjunction of SSA is unsat [2018-06-20 14:02:08,886 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 14:02:08,886 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 14:02:08,886 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 14:02:08,892 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-20 14:02:08,979 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-20 14:02:08,979 INFO ]: Conjunction of SSA is unsat [2018-06-20 14:02:08,983 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-20 14:03:12,765 INFO ]: Timeout while computing interpolants [2018-06-20 14:03:12,966 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 14:03:12,966 WARN ]: Verification canceled [2018-06-20 14:03:12,970 WARN ]: Timeout [2018-06-20 14:03:12,970 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.06 02:03:12 BoogieIcfgContainer [2018-06-20 14:03:12,970 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-20 14:03:12,971 INFO ]: Toolchain (without parser) took 71335.84 ms. Allocated memory was 307.8 MB in the beginning and 2.7 GB in the end (delta: 2.4 GB). Free memory was 261.1 MB in the beginning and 942.4 MB in the end (delta: -681.3 MB). Peak memory consumption was 2.7 GB. Max. memory is 7.1 GB. [2018-06-20 14:03:12,972 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 307.8 MB. Free memory is still 273.2 MB. There was no memory consumed. Max. memory is 7.1 GB. [2018-06-20 14:03:12,973 INFO ]: ChcToBoogie took 90.41 ms. Allocated memory is still 307.8 MB. Free memory was 261.1 MB in the beginning and 257.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 7.1 GB. [2018-06-20 14:03:12,974 INFO ]: Boogie Preprocessor took 41.25 ms. Allocated memory is still 307.8 MB. Free memory was 257.2 MB in the beginning and 256.2 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 7.1 GB. [2018-06-20 14:03:12,974 INFO ]: RCFGBuilder took 291.56 ms. Allocated memory is still 307.8 MB. Free memory was 256.2 MB in the beginning and 245.1 MB in the end (delta: 11.1 MB). Peak memory consumption was 11.1 MB. Max. memory is 7.1 GB. [2018-06-20 14:03:12,975 INFO ]: TraceAbstraction took 70904.34 ms. Allocated memory was 307.8 MB in the beginning and 2.7 GB in the end (delta: 2.4 GB). Free memory was 244.1 MB in the beginning and 942.4 MB in the end (delta: -698.3 MB). Peak memory consumption was 2.7 GB. Max. memory is 7.1 GB. [2018-06-20 14:03:12,978 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 307.8 MB. Free memory is still 273.2 MB. There was no memory consumed. Max. memory is 7.1 GB. * ChcToBoogie took 90.41 ms. Allocated memory is still 307.8 MB. Free memory was 261.1 MB in the beginning and 257.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 7.1 GB. * Boogie Preprocessor took 41.25 ms. Allocated memory is still 307.8 MB. Free memory was 257.2 MB in the beginning and 256.2 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 7.1 GB. * RCFGBuilder took 291.56 ms. Allocated memory is still 307.8 MB. Free memory was 256.2 MB in the beginning and 245.1 MB in the end (delta: 11.1 MB). Peak memory consumption was 11.1 MB. Max. memory is 7.1 GB. * TraceAbstraction took 70904.34 ms. Allocated memory was 307.8 MB in the beginning and 2.7 GB in the end (delta: 2.4 GB). Free memory was 244.1 MB in the beginning and 942.4 MB in the end (delta: -698.3 MB). Peak memory consumption was 2.7 GB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 13 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 28242 quantified variables from 12 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 70.8s OverallTime, 5 OverallIterations, 5 TraceHistogramMax, 0.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 28 SDtfs, 4 SDslu, 61 SDs, 0 SdLazy, 26 SolverSat, 11 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 48 GetRequests, 23 SyntacticMatches, 6 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 1.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=13occurred in iteration=4, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 4 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 5.4s InterpolantComputationTime, 61 NumberOfCodeBlocks, 61 NumberOfCodeBlocksAsserted, 10 NumberOfCheckSat, 54 ConstructedInterpolants, 0 QuantifiedInterpolants, 1290 SizeOfPredicates, 15 NumberOfNonLiveVariables, 399 ConjunctsInSsa, 64 ConjunctsInUnsatCore, 7 InterpolantComputations, 1 PerfectInterpolantSequences, 0/20 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/chc-lia-0124.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-20_14-03-12-993.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/chc-lia-0124.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-20_14-03-12-993.csv Completed graceful shutdown